// SequenceSearch.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include"SequenceList.h"

int main()
{
    List* list = InitList(5);
    ListAdd(list, 3);
    ListAdd(list, 4);
    ListAdd(list, 5);
    ListAdd(list, 2);
    ListAdd(list, 1);  

    ListPrint(list);
    
    /*
    * 平均查找长度
    * 是查找算法的查找成功时的平均查找长度的缩写，是为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值
    * ASL = ￡(n, n = 1) P(i) * C(i)
    * P(i): 查找表中第i个记录的概率
    * C(i): 关键字与给定值相等的第i个记录时，和给定值 进行过比较的关键字个数
    * 
    * 顺序查找 ASL
    * ASL = 1 * 1/n + 2 * 1/n + .... + n * 1/n
    *     = (1 + n) n / 2 * 1 / n = (1 + n) / 2
    */

    printf("顺序查找数据 3, 在位置 : %d\n", SequencetialSearch(list, 3)); 
    printf("哨兵顺序查找数据 4, 在位置 : %d\n", SequencetialSearchGuard(list, 4));
    printf("哨兵顺序查找数据 1, 在位置 : %d\n", SequencetialSearchGuard(list, 1));
}